from sage.all import *
import sys

n = 91717197306065801430692774296739087369692505805873730729014813677164858033475119219496549179322145782790263228034134781592967028480301579462111507372893508636592832600206391905790511488678949157112322777098684707325311891056750963286494634489093620270797637437274546909400418496263799669541769586017282231886023275686719495040493703402244867906367008837217453500300992995258096509545406775279177918160331853363991834113918051468978309081085686108283547874975768959542753094631595260890420558364636303078263220001513817844063960023424429484568985727987064710176511050208253838039386390968276801658300795687804601169987051671314061987254212363117325786734328360418591971610392966867659045907550755979167652038093091970078722854251659581538266806207906127491377972897441916942048136016416739633568604447564119372465662628724153812001753748410162478969725179843125714619352895967577899670208386148053595763674920185320834513587
c = 23108886533446570872020909755641900356947493847891044150804220862211486326491971706435448761622169415139661878928224913976333510314336448940337410429358364930668139829928592529668292963027387644469478288972914226815180690096771951746297286742213772233222849955148332178748604312396371718173812097510261044590926364130009538926786724953078781179023997612212615391343990439872921361528517747700275371695937658958128759666192424696264306876062180553241654472104865168758800754398829940157821429340806270860129304323452617932918962620283443237641173000603550358778106863474195136519485531345183377464308279092379760531364034030760854381522739756338905572215597123741549768493220177173389970868309425490948920216103262840379934097953147391955089537672609825176272093624601261813994392924293258762828299757881538282236959849884840306493309190697864334857950458623192423892550873631196964551924143834939270415901966374552371883381
gift1 = 513
gift2 = 5077110719426498428662246006638349628986894614097694065336047422264042823893900747327210766546701290926253205743419412459378571920759093322149140413682875156857171051511499793127787270654329155934268596972449238336868326196360992252498463385

def find_p():
    # 遍历x从0到1023
    for x in range(0, 1024):
        k = (x << 10) + gift1  # k = x*2^10 + 513
        B = (gift2 << 20) + k  # B = gift2左移20位 + k
        # 构造多项式环
        PR.<a> = PolynomialRing(Zmod(n), implementation='NTL')
        f = a * (2**820) + B
        f = f.monic()
        # 寻找小根，X=2^204，beta=0.33
        try:
            roots = f.small_roots(X=2**204, beta=0.33, epsilon=0.02)
            if roots:
                a_val = roots[0]
                p_candidate = int(a_val) * (2**820) + B
                if n % p_candidate == 0:
                    print(f"Found p with x={x}")
                    return p_candidate
        except KeyboardInterrupt:
            raise
        except:
            continue
    return None

p = find_p()
if p is None:
    print("Failed to find p")
    sys.exit(1)

print("p =", p)

# 分解qr = n // p
qr = n // p

# 寻找q和r，其中r是next_prime(q)
# 计算qr的平方根作为q的估计
q_approx = isqrt(qr)
while True:
    if qr % q_approx == 0:
        r_candidate = qr // q_approx
        if next_prime(q_approx) == r_candidate:
            q = q_approx
            r = r_candidate
            break
    q_approx = next_prime(q_approx)

print("q =", q)
print("r =", r)

# 计算phi(n)
phi = (p-1) * (q-1) * (r-1)
e = 0x10001
d = inverse_mod(e, phi)

# 解密
m = pow(c, d, n)
flag = bytes.fromhex(hex(m)[2:])
print("Flag:", flag)
